1. Field of the Invention
The invention is related to the field of computer communications and more particularly to achieving synchronization of a Content Induced Transaction Overlap (CITO) communication channel.
2. Description of the Prior Art
Various types of multiple-access channel communication systems are known in the art. These communication systems may conveniently be divided into two distinct types, the Time Division Multiple Access (TDMA) systems, and the Carrier Sensed Multiple Access (CSMA) systems. In time Division Multiple Access systems, such as disclosed by Hopkins et al in U.S. Pat. No. 4,161,786; Lowe, Jr. in U.S. Pat. No. 4,199,662 or White et al in U.S. Pat. No. 4,199,661 the transmission channel capacity is divided into time slots during which identified transmitters are allowed to transmit their information over the communication network. Each transmitter is assigned a specific time slot so that each transmitter in turn will have an opportunity to transmit its information. In Carrier Sensed Multiple Access systems, such as disclosed by Eswaran et al in U.S. Pat. No. 4,292,623, Herzog, U.S. Pat. No. 4,199,663, or Spracklen et al in U.S. Pat. No. 4,337,465, each transmitter detects when the communication channel is idle, then after a predetermined period of time, attempts to transmit its information. Typically, the waiting period depends on the assigned priority of the transmitter.
The problem with the Time Division Multiple Access system is that often a particular transmitter may not have any information to transmit during its allotted time slot, while other transmitters may generate two or more messages in the period between their allotted time slots. Therefore some transmission time slots are wasted while other messages are delayed while awaiting access to the common transmission line. This problem is partially overcome by the Carrier Sensed Multiple Access system under light or moderate loads. However under high message traffic conditions, the probability of simultaneous access to the common transmission line rises sharply, and excessive amounts of time are wasted resolving priority differences of the involved transmitters.
A Content Induced Transaction Overlap Communication System (CITO) as disclosed by Walter et al in U.S. Pat. No. 4,493,074 and assigned to the same assignee as the present invention is hereby incorporated by reference and, is designed to overcome these problems. Such a system is designed for transmitting data from a plurality of senders to a receiver over a single communication channel. Each sender has a data register which stores the multiple bit data word to be transmitted, a word boundary register which stores the number of bits in the data word and a bit position register. The transmission begins with each sender transmitting the highest order bit stored in the data register. Bits are transmitted on the channel in an overlapped manner such that the channel state is the logical sum or product of the transmitted bits. Using single phase representation, where a zero bit is transmitted as a finite signal level and a one bit is transmitted as a null signal level, the composite channel states are accordingly 0 or 1.
The senders each then compare the state of the communication channel with their transmitted bit to determine if they are the same. If the state of the communication channel is the same as the transmitted bit, the sender transmits its next highest bit and decrements its word boundary and bit position registers. However, if the state of the communication channel is different from its transmitted bit, the sender terminates the transmission of its remaining bits but continues to monitor the communication channel and decrement its word boundary register for each bit transmitted on the communication channel. At the end of the transmission of the data word, indicated by the word boundary register being decremented to zero, each sender enters into bit competition with all of the senders based on the content of its bit position register when it stopped transmitting to determine if it has lexicographically the next smallest data word. If it has, it initiates the sending of its remaining data bits. However, if it doesn't have lexicographically the next smallest data word, the sender waits until the end of the transmission of the current data word and re-enters the bit competition. This cycle repeats until all of the senders have completed the transmission of all the bits in their data words. At this point, all the bit position registers have zero bits and no sender performs in the bit competition. The senders recognize the termination of the current data bucket (collection of data bits in the different senders) and the transmission of the next data bucket can begin after synchronization.
The problem of achieving synchronization in CITO communication arises because the transmission framework contains bits of different meanings: bit competitions or word fragments. A device reviewing a CITO transmission has to be able to recognize the boundaries between these types of messages. This problem appears throughout A CITO channel's full cycle of operation: when the system initializes (bootstrapping), when a new device starts transmitting on the communication channel (dynamic attachment), and when a device fails and has to resynchronize.
The prior art's solutions for synchronization of multi-access communication channels, which do not have specially reserved states different from information carrying signals, is to employ a unique synchronization pattern. As soon as the transmission pattern is different from any possible combination of symbols which appear in the course of regular transmission, a reference point is provided for a receiving device.
There are two basic approaches to organizing a particular pattern in the CITO channel for the purpose of synchronization. The first approach is to use an inter data bucket "silence" (string of 1's) of a length (r+log r) appearing on the communication channel at the end of the data bucket. The second approach is to introduce bit stuffing by suppressing artificially, strings of "1's", having a length greater than log r, so that a pattern of log r silent slots of "1's", can serve as an indicator of the data bucket's end.
In both of these approaches a device seeking synchronization has to wait until the end of the data bucket. The latter method uses a shorter synchronization pattern but it requires extra hardware that is utilized solely for synchronization purposes.
A variety of other synchronization techniques exist, one of which is disclosed by Whiteside et al in U.S. Pat. No. 4,330,826. This Synchronizer and Synchronization System For Multiple Computer Systems works on the principal of obtaining a "voted sampling number" when a predetermined number of computers send messages containing the same sampling number. In the present invention, the synchronization is achieved through a mechanism of interrupt which can be performed by each of the devices without an agreement protocol. U.S. Pat. No. 4,621,289 by Bart et al discloses an improvement in a television receiver sync filter which represents an attempt to overcome currently existing problems especially in the areas of weak, noisy, and non-standard video signals. The present invention of active synchronization, however, deals mostly with the organizational aspects of the problem and assumes standard environmental digital signals. U.S. Pat. No. 4,720,828 discloses an I/O handler for a computer. This device passes data between the computer and devices external to the computer. Bit synchronization is accomplished by the dedication of one of the several channel intervals to the transmission of a special sync sequence. In the present invention, however, there is no dedicated intervals for synchronization, it can be initiated within a regular transmission at any time interval. U.S. Pat. No. 4,733,353 by Jaswa discloses a frame synchronization method and apparatus for multiply redundant computers. With this invention, each computer periodically executes a frame synchronization procedure in which it sequentially assumes a plurality of different operating states during which it pauses in the execution of a task it was performing readies itself for synchronization and synchronizes itself with one of the other systems. In the present invention, however, the process of synchronization can be performed at arbitrary moments of time and by the initiation of any of the computers in the system. In U.S. Pat. No. 4,323,966 by Whiteside et al, an operations controller for a fault-tolerant multiple computer system is disclosed. This system uses a master-slave concept and the operation controller is utilized for scheduling various tasks. The synchronization is organized by a conventional message passing method which is different than that disclosed in the present invention.